The present invention applies filters to digitized images so that the images can be simplified. Because filtering techniques are pervasive in many different image-processing applications, common filters and their usual applications are now distinguished so that the filters according to the invention, and their application to image simplification techniques are not confused with prior art other image processing applications. Image simplification according to the invention is not concerned with noise, smoothness, edge, classification, or reconstruction filtering, which are now distinguished in greater detail.
Noise Filtering
Filtering can remove noise contaminations from digital images. Some common types of the noise removal filters are low-pass filters, neighborhood-averaging filters, median filters, mode filters, reconstruction filters, enhancement filters, morphological filters, Laplacian filters, Gaussian filters, to name but a few. Gaussian filters remove high-frequency noise but cause blurring. Gaussian filters are the most common noise filters used in image reconstruction, and are described in further detail below. There, a normal convolution kernel is applied to localized regions of pixels of the image. A harmonic filter is a non-linear mean filter that is also good for removing Gaussian noise and positive outliers.
Smoothness Filtering
Low pass filtering, otherwise known as “smoothing,” removes high spatial frequency noise from a digital image. Noise is often introduced during analog-to-digital conversion as a side effect of the physical conversion of analog patterns of light energy into digital electrical signals. Low-pass filters usually move some sort of moving window operator across the image to affect all the pixels in the image. The operator affects one pixel of the image at a time, changing its value by some function of a local region of pixels. Neighborhood-averaging filters replace the value of each pixel by a weighted-average of the pixels in some neighborhood near the pixel. If all the weights are equal, then the operator is a mean filter. Morphological filters can also be used to remove image irregularities. A special kind of morphological filter is a dilation filter that can be used to smooth small regions of pixels with negative gray-levels
Edge Filtering
Median filters change each pixel value by the median of its neighboring pixels, i.e., the value such that 50% of the values in the neighborhood are above the pixel's value, and 50% of the values are below the pixel's value. This can be difficult and costly to implement due to the need for sorting the values. However, this method is generally very good at preserving edges. Median filters remove long tailed impulsive noise with a minimum amount blurring. Median filters are scalable, have constant additivity, but are non-linear. Therefore, median filters are hard to analyze. A Laplacian filter is a generalization of the second derivative and is also usually reserved for edge filtering.
Classification Filtering
Mode filters replace each pixel value by the value of the most common neighboring pixel. This is a particularly useful filter for image classification applications where the pixels correspond to objects that must be placed into a class. The mode filter is also used for remote sensing, for example, here the classes are some type of terrain, crop type, water, etc.
Reconstruction Filtering
In reconstruction filtering, an image is restored based on some knowledge of the type of degradation the image has undergone. Filters that enable image reconstruction are often called “optimal filters.” Image reconstruction can also remove noise while preserving some local constraints such as edges that generally correspond to object boundaries. Reconstruction can be considered a smoothing operation that does not adversely affect object boundaries.
Frequently, images are reconstructed to better estimate content of the images. By regularizing or smoothing the brightness of the images, the reconstruction works as an independent smoothness constraint in disparity estimation, surface model fitting, and optical flow based motion estimation processes, see Black et al., “The outlier process: unifying line process and robust statistics,” IEEE Conf. on Computer Vision and Pattern Recognition, Seattle, (1994), and Black et al., “Estimating optical flow in segmented images using variable-order parametric models with local deformations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, (1998).
Image reconstruction is also applicable to modeling spatial discontinuities, see Geman et al., “Constraint reconstruction and recovery of discontinuities,” IEEE Transactions on Pattern Analysis and Machine Intelligence, (1992), and for problems such as surface recovery. Image reconstruction is also used for image enhancement, see Geiger et al., “Parallel and deterministic algorithms from MRF's: Surface Reconstruction,” IEEE Transactions on Pattern Analysis and Machine Intelligence, (1991). Enhancement filtering attempts to improve the subjectively measured quality of an image for machine interpretability. Enhancement filters are generally heuristic and application oriented.
Image Simplification
In contrast with the above image processing applications, image simplification is a tool for reducing the complexity of image patterns for various purposes including segmentation, editing, animation and manipulation, low bit rate object-based image compression. Image simplification can also be employed in scalable video coders to adapt video content to network constraints. Image simplification may be used to decrease the spatial color variance and color dynamic range. In addition, textures within the boundaries of objects can be suppressed. Therefore, it is desired to provide a method that is specifically designed for image simplification.
Downhill Simplex Minimization
As described below, the method according to the invention uses a minimization technique. One simple minimization technique is introduced here. Downhill simplex minimization was first described by Nelder and Mead in “The downhill simplex method,” Computer Journal, 7:391–398, 1965. The method evaluates functions instead of taking derivatives in order to determine a (local) minimum. The downhill simplex method is frequently the best method to use in case of parameter dimensions higher than twenty. The simplex method can be explained in terms of geometric figures.
A simplex is a geometrical figure of N+1 vertices in N dimensions, and all their interconnecting edges, line segments, or polygonal faces, and the like. In two dimensions, a triangle is one example a simplex, and in three dimensions, a tetrahedron. Of interest are non-degenerate simplexes, i.e., simplexes which enclose a finite N-dimensional volume. If any point of a non-degenerate simplex is taken as the origin, then the N other points define vector directions that span the N-dimensional vector space.
The method then makes it way “downhill” from a starting vertex, through the unimaginable complexity of an N-dimensional topography, until it encounters, at least, a minimum vertex. The method does this by taking a series of steps and moving a vertex with a maximum value through the opposite face of the simplex to a lower location having a lower value. These steps are called reflections, and they are constructed to conserve the volume of the simplex, and hence maintain its non-degeneracy. When it can do so, the method expands the simplex in one or another direction to take larger steps. When it reaches a “valley floor,” the method contracts itself in the transverse direction and tries to “ooze” down the valley. If there is a situation where the simplex is trying to “pass through the eye of a needle,” it contracts itself in all directions, pulling itself in around its minimum or “best” vertex.
The simplex method differs from the well-known and widely used Levenberg-Marquardt and Gauss-Newton methods in that the simplex method does not use derivatives. Therefore, the simplex method has better convergence properties because it is much less prone to finding false minima. One of the more remarkable features of the downhill simplex minimization method is that it requires no divisions. Thus, the “division-by-zero” problem is avoided.